package com.zz.array;
/**
 *
 * @author 张哲
 * @email a252013135@163.com
 * @date 2024/9/12 14:40
 *
 * ⼆维数组中的查找：
 * 在⼀个⼆维数组中（每个⼀维数组的⻓度相同），每⼀⾏都按照从左到右递增的顺序排序，每⼀列都按照
 * 从上到下递增的顺序排序。请完成⼀个函数，输⼊这样的⼀个⼆维数组和⼀个整数，判断数组中是否含有
 * 该整数。
 *
 * 输⼊⼀个数组：
 * num[ 3 ][ 4 ] = [
 * 1 , 4 , 6 , 28 ,
 * 2 , 7 , 32 , 30 ,
 * 10 , 11 , 67 , 79
 * ]
 *
 * 需要查找⼀个数字 32 ，则返回 true。
 */
public class Offer4 {
    /**
     * 暴力破解
     *
     * @param target
     * @param array
     * @return
     */
    public boolean find1(int target, int[][] array) {
        if (array == null || array.length == 0) {
            return false;
        }
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                if (array[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }


    /**
     * ⽐较查找法
     * @param target
     * @param array
     * @return
     */
    public boolean find2(int target, int[][] array) {
        if(array == null || array.length == 0 || array[0].length == 0) {
            return false;
        }
        int size = array.length;
        int length = array[0].length;
        int i, j;
        for (i = size - 1, j = 0; i >= 0 && i < size && j >= 0 && j <
                length; ) {
            if (array[i][j] == target) {
                return true;
            }
            if (array[i][j] < target) {
                j++;
                continue;
            }
            if (array[i][j] > target) {
                i--;
                continue;
            }
        }
        return false;
    }
}
